package Random_Problem.Day_0203;

/**
 * @author zxc
 * @date 2023/02/03 10:06
 **/

import java.util.*;

/**
 * 题目 ：根据身高来重建队列
 * 题目详述 ：
 * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。
 * 每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
 * 请你重新构造并返回输入数组people 所表示的队列。
 * 返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
 *
 * 提示：
 * 1 <= people.length <= 2000
 * 0 <= hi <= 106
 * 0 <= ki < people.length
 * 题目数据确保队列可以被重建
 *
 */
public class ReconstructQueue {
    /**
     * 思路 ：
     *
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        // 对于people数组进行排序;
        /**
         *  排序规则 ：
         * （1）由于是根据people[0]进行从大到小排序，同时需要将people中元素重新进行排序;
         * （2）若是两个元素的people[0]是相同的话，则需要根据people[1]进行从小到大的排序;
         */
        Arrays.sort(people , (p1 , p2) ->{
            if(p1[0] == p2[0]){
                return p1[1] - p2[1];
            }
            else {
                return p2[0] - p1[0];
            }
        });

        List<int[]> queue = new ArrayList<>();
        for (int[] person : people) {
            // 根据排序过元素的person[1]进行插入;
            queue.add(person[1] , person);
        }
        // List集合，转化为Array数组;
        return queue.toArray(new int[people.length][]);
    }
}
